package com.code.test.dance;

import com.code.test.second.link.SNode;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
 * <p>
 * 两个链表 中间相连，判断第-一个相连的位置。
 * <p>
 * 面试题 02.07. 链表相交
 * * 同：160.链表相交
 * * <p>
 * * 力扣题目链接
 * * <p>
 * * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * * <p>
 * * 图示两个链表在节点 c1 开始相交：
 */
public class LinkIntersection {

    public static void main(String[] args) {
        LinkNode headA21 = new LinkNode(21);
        LinkNode headA22 = new LinkNode(22);
        LinkNode headA23 = new LinkNode(23);
        LinkNode n4 = new LinkNode(24);
        LinkNode n5 = new LinkNode(99);
        LinkNode n6 = new LinkNode(98);
        LinkNode n7 = new LinkNode(100);

        headA21.setNext(headA22);
        headA22.setNext(headA23);
        headA23.setNext(n4);


        n4.setNext(n5);
        n5.setNext(n6);
        n6.setNext(n7);

        /**
         * ========================================
         */

        LinkNode headB11 = new LinkNode(11);
        LinkNode headB12 = new LinkNode(12);
        LinkNode headB13 = new LinkNode(13);
        LinkNode headB14 = new LinkNode(14);

        headB11.setNext(headB12);
        headB12.setNext(headB13);
        headB13.setNext(headB14);
        headB14.setNext(n4);

        LinkNode tempHeadA = headA21;
        LinkNode tempHeadB = headB11;
        while (headA21 != null) {
            System.out.print(headA21.getVal() + "→");
            headA21 = headA21.getNext();
        }

        System.out.println("");
        while (headB11 != null) {
            System.out.print(headB11.getVal() + "→");
            headB11 = headB11.getNext();
        }

        System.out.println("");

        LinkNode node = findSampleNode(tempHeadA, tempHeadB);

        while (node != null) {
            System.out.print(node.val + "→");
            node = node.next;
        }
        System.out.println("");

    }

    public static LinkNode findSampleNode(LinkNode nodeA, LinkNode nodeB) {

        LinkNode s1 = nodeA;
        LinkNode s2 = nodeB;

        while (s1 != s2) {
            s1 = s1 != null ? s1.next : nodeB;
            s2 = s2 != null ? s2.next : nodeA;
        }
        return s1;
    }
}
